Міністерство освіти і науки, молоді та спорту України Полтавський національний технічний університет Ім. Юрія Кондратюка Факультет інформаційних та телекомунікаційних технологій і систем Курсова робота з дисципліни «Теория алгоритмів» ЗМІСТ Постановка задачі 3 Вступ 4 Теорія 5 Нормальний алгоритм Маркова 5 Десяткова система числення. 9 Шістнадцяткова система числення. 10 Приклади 12 Практична реалізація 13 Лістинг програми 14 Результати роботи програми 23 Висновки 25 Література 26 ПОСТАНОВКА ЗАДАЧІ Варіант 19 (Рак 202-ТН)  Скласти нормальний алгоритм Маркова для перетворення числа в десятковій системі числення в систему з основою 16 (наприклад Вхідні дані: 255 Вихідні дані: FF). Вимоги до програми: Можливість перегляду коду нормального алгоритму Маркова. Покрокова візуалізація роботи програми. Інтерфейс під Windows! Не консольний.   ВСТУП Вважається, що за допомогою нормальних алгоритмів Маркова (алгорифмів) можливо задати будь-який алгоритм. У межах даноії курсової роботи складемо нормальний алгоритм Маркова для перетворення числа з десяткової системи числення в систему з основою 16. Десятковою системою числення у повсякденному житті користується більша (якщо не вся) частина населення планети. Шістнадцяткову використовують в основному в обчислювальній техніці і програмуванні. Перед програмістами часто стоїть задача перетворення чисел з однієї системи числення в іншу. Для перевірки роботи нормального алгоритму Маркова напишемо емулятор на мові програмування високого рівня Java. Java — объектно-ориентированный язык программирования, разработанный компанией Sun Microsystems (в последующем, приобретённой компанией Oracle). Приложения Java обычно компилируются в специальный байт-код, поэтому они могут работать на любой виртуальной Java-машине (JVM) независимо от компьютерной архитектуры. Дата официального выпуска — 23 мая 1995 года. Для розробки своєї програми я використав середовище програмування Eclipse. Eclipse (вимовляється «і-клі́пс», від англійського «затемнення») — вільне модульне інтегроване середовище розробки програмного забезпечення. Розробляється і підтримується Eclipse Foundation. Написаний в основному на Java, і може бути використаний для розробкизастосунків на Java і, за допомогою різніх плагінів, на інших мовах програмування, включаючи Ada, C, C++, COBOL, Perl, PHP, Python, R, Ruby(включно з каркасом Ruby on Rails), Scala, Clojure та Scheme. Середовища розробки часто називають Eclipse ADT (Ada Development Toolkit) для Ada, Eclipse CDT для C/C++, Eclipse JDT для Java, Eclipse PDT для PHP. ТЕОРІЯ Нормальний алгоритм Маркова Для формалізації поняття алгоритму російський математик А.А. Марков запропонував використовувати асоціативні обчислення. Розглянемо деякі поняття асоціативного обчислення. Нехай є алфавіт (кінцевий набір різних символів). Складові його символи будемо називати літерами. Будь кінцева послідовність літер алфавіту (лінійний їх ряд) називається словом в цьому алфавіті.Розглянемо два слова N і М в деякому алфавіті А. Якщо N є частиною М, то говорять, що N входить в М.Задамо в деякому алфавіті кінцеву систему підстановки N - М, S - Т ,..., де N, M, S, Т, ... - Слова в цьому алфавіті. Будь-яку підстановку NM можна застосувати до деякого слова К наступним способом: якщо в К є одне або кілька входжень слова N, то будь-яке з них може бути замінено словом М, і, навпаки, якщо є входження М, то його можна замінити словом N.Наприклад, в алфавіті А = {а, b, с} є слова N = ab, М = bcb, К = abcbcbab, Замінивши в слові К слово N на М, одержимо bcbcbcbab або abcbcbbcb, і, навпаки, замінивши М на N, отримаємо aabcbab або аbсаbаb.Підстановка ab - bcb неприпустима до слова bacb, так як не ab, ні bcb не входить в це слово. До отриманих за допомогою допустимих підстановок слів можна знову застосувати допустимі підстановки і т.д. Сукупність усіх слів у даному алфавіті разом з системою допустимих підстановки називають асоціативним обчисленням. Щоб задати асоціативне числення, досить задати алфавіт і сис...